package com.javabasic.algorithm.sword_of_offer;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/16 2:39 下午
 */
public class 剑指_Offer_25_合并两个排序的链表 {


    /**
     * 类似数组合并
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode preHead = new ListNode(-1), newHead = preHead;
        ListNode preHead1, preHead2;

        preHead1 = l1;
        preHead2 = l2;

        while (preHead1 != null && preHead2 != null) {

            if (preHead1.val <= preHead2.val) {
                newHead.next = preHead1;
                preHead1 = preHead1.next;
            } else {
                newHead.next = preHead2;
                preHead2 = preHead2.next;
            }
            newHead = newHead.next;
        }

        while (preHead1 != null) {
            newHead.next = preHead1;
            newHead = newHead.next;
            preHead1 = preHead1.next;
        }

        while (preHead2 != null) {
            newHead.next = preHead2;
            newHead = newHead.next;
            preHead2 = preHead2.next;
        }

        return preHead.next;
    }
}
